package day_2022_12_to_3.year2023;

import java.util.Deque;
import java.util.LinkedList;
import java.util.List;

/**
 * @author haomin
 * @date 2023/03/20 20:16
 **/
public class Day3_20_Review {
    class Solution1 {
        public ListNode reverseKGroup(ListNode head, int k) {
            if(head == null || head.next == null) return head;
            int size = 0;
            ListNode dummyHead = new ListNode(-1), cur = head, pre, next;
            while(cur != null) {cur = cur.next; size ++;}
            int count = size / k;
            dummyHead.next = head;
            cur = head; pre = dummyHead;
            while(count-- > 0) {
                for(int i = 0; i < k-1; ++i) {
                    next = cur.next;
                    cur.next = next.next;
                    next.next = pre.next;
                    pre.next = next;
                }
                pre = cur;
                cur = pre.next;
            }
            return dummyHead.next;
        }
    }

    class Solution2 {
        public ListNode reverseList(ListNode head) {
            if(head == null || head.next == null) return head;
            ListNode dummyHead = new ListNode(-1);
            ListNode cur = head, next;
            while(cur != null) {
                next = cur.next;
                cur.next = dummyHead.next;
                dummyHead.next = cur;

                cur = next;
            }
            return dummyHead.next;
        }
    }

    class Solution3 {
        public ListNode reverseList(ListNode head) {
            if(head == null || head.next == null) return head;
            ListNode pre = null, cur = head, next;
            while(cur != null) {
                next = cur.next;
                cur.next = pre;

                pre = cur;
                cur = next;
            }
            return pre;
        }
    }

    class Solution4 {
        public ListNode reverseList(ListNode head) {
            if(head == null || head.next == null) return head;
            ListNode second = head.next;
            ListNode newHead = reverseList(head.next);

            second.next = head;
            head.next = null;
            return newHead;
        }
    }

    class Solution5 {
        public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
            if(list1 == null) return list2;
            if(list2 == null) return list1;
            if(list1.val < list2.val) {
                ListNode next = mergeTwoLists(list1.next, list2);
                list1.next = next;
                return list1;
            }else {
                ListNode next = mergeTwoLists(list1, list2.next);
                list2.next = next;
                return list2;
            }
        }
    }

    class Solution6 {
        public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
            if(list1 == null) return list2;
            if(list2 == null) return list1;

            ListNode dummyHead = new ListNode(-1);
            ListNode cur = dummyHead;
            while(list1 != null && list2 != null) {
                if(list1.val < list2.val) {
                    cur.next = new ListNode(list1.val);
                    list1 = list1.next;
                }else {
                    cur.next = new ListNode(list2.val);
                    list2 = list2.next;
                }
                cur = cur.next;
            }
            if(list1 == null) cur.next = list2;
            if(list2 == null) cur.next = list1;
            return dummyHead.next;
        }
    }

    class Solution7 {
        public int[] levelOrder(TreeNode root) {
            if(root == null) return new int[0];
            List<Integer> list = new LinkedList<>();
            Deque<TreeNode> q = new LinkedList<>();
            q.offer(root);
            while(!q.isEmpty()) {
                int size = q.size();
                for(int i = 0; i < size; ++i) {
                    TreeNode cur = q.poll();
                    list.add(cur.val);
                    if(cur.left != null) q.offer(cur.left);
                    if(cur.right != null) q.offer(cur.right);
                }
            }
            return list.stream().mapToInt(Integer::intValue).toArray();
        }
    }

}